package com.ronz.search;

/**
 * @Description 插值查找算法
 * @Author Ronz
 * @Date 2021/1/13 19:51
 * @Version 1.0
 */
public class No3_insertValueSearch {

    public static void main(String[] args) {
        int[] arr = {2,5,8,9,11,45,67,88,188};
        int index = insertValueSearch(arr, 0, arr.length-1, 11);
        System.out.println("目标元素在数组中索引为：" + index);
    }

    /**
     * 插值查找算法
     * @param arr   从此数组中查找
     * @param left  查找范围左边界
     * @param right 查找范围右边界
     * @param findValue 目标元素
     * @return int  目标元素在数组中的索引
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findValue){
        if (right < left){  // 如果没找到，要退出
            return -1;
        }
        int mid = left + (right-left)*(findValue-arr[left])/(arr[right]-arr[left]); // 计算查找点
        if (findValue > arr[mid]){  // 如果大于查找点，就向右递归
            return insertValueSearch(arr, mid+1, right, findValue);
        }else if (findValue < arr[mid]){    // 如果小于查找点，就向左递归
            return insertValueSearch(arr, left, mid-1, findValue);
        }else{  // 如果等于查找点，就返回索引值
            return mid;
        }
    }

}
